Over the years, different meanings have been associated to the wordconsistency in the distributed systems community. While in the '80s"consistency" typically meant strong consistency, later defined also aslinearizability, in recent years, with the advent of highly available andscalable systems, the notion of "consistency" has been at the same time bothweakened and blurred. In this paper we aim to fill the void in literature, by providing astructured and comprehensive overview of different consistency notions thatappeared in distributed systems, and in particular storage systems research, inthe last four decades. We overview more than 50 different consistency notions,ranging from linearizability to eventual and weak consistency, definingprecisely many of these, in particular where the previous definitions wereambiguous. We further provide a partial order among different consistencypredicates, ordering them by their semantic "strength", which we believe willreveal useful in future research. Finally, we map the consistency semantics todifferent practical systems and research prototypes. The scope of this paper is restricted to non-transactional semantics, i.e.,those that apply to single storage object operations. As such, our papercomplements the existing surveys done in the context of transactional, databaseconsistency semantics.
展开▼
